package 笔试题.pdd;

import java.util.Scanner;

public class t3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] w = new int[5000];
        int[] d = new int[5000];
        int[] dp = new int[15000];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            d[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= 0; j--) {
                if (j >= w[i])
                    dp[j] = Math.max(dp[j], dp[j - w[i]] + d[i]);
            }
        }
        System.out.println(dp[m]);
    }

    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] w = new int[5000];
        int[] d = new int[5000];
        int[] dp = new int[15000];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            d[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= 0; j--) {
                if (w[i] >= 0) {
                    if (j >= w[i]){
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + d[i]);
                    }
                }else {
                    w[i] = -w[i];
                    if (j >= w[i]) {
                        dp[j] = Math.max(dp[j], dp[j + w[i]] + d[i]);
                    }
                }
            }
        }
        System.out.println(dp[m]);
    }
}
